package sort;
//挖坑法
public class quick2 {
    public static void a(int [] arr,int left,int right){
        if (left>=right){
            return;
        }
        int div=b(arr,left,right);
//        左边递归
        a(arr,left,div);
//        右边递归
        a(arr,div+2,right);
    }
    public static int b(int[]arr,int left,int right){
        int cur=arr[left];
        int i=left,j=right;
        while (i<j){
            while (i<j&&arr[j]>=cur){
                j--;
            }
            arr[i]=arr[j];
            while (i<j&&arr[i]<=cur){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=cur;
        return i-1;
    }
}
